package Double_pointer;

import java.util.*;
//双指针

class Interval {
      int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }
 }
public class Solution {
    /*最长无重复子数组*/

    /*反转字符串*/
    public String solve (String str) {
        StringBuilder stringBuilder=new StringBuilder();
        for (int i = str.length()-1; i >=0  ; i--) {
            stringBuilder.append(str.charAt(i));
        }
        return stringBuilder.toString();
    }

   /* 合并区间
    给出一组区间，请合并所有重叠的区间。请保证合并后的区间按区间起点升序排列。*/

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<>();
        //去除特殊情况
        if(intervals.size() == 0)
            return res;
        //重载比较，按照区间首排序
        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval o1, Interval o2){
                if(o1.start != o2.start)
                    return o1.start - o2.start;
                else
                    return o1.end - o2.end;
            }
        });
        //放入第一个区间
        res.add(intervals.get(0));
        int count = 0;
        //遍历后续区间，查看是否与末尾有重叠
        for(int i = 1; i < intervals.size(); i++){
            Interval o1 = intervals.get(i);
            Interval origin = res.get(count);
            if(o1.start > origin.end){
                res.add(o1);
                count++;
                //区间有重叠，更新结尾
            }else{
                res.remove(count);
                Interval s = new Interval(origin.start, o1.end);
                if(o1.end < origin.end)
                    s.end = origin.end;
                res.add(s);
            }
        }
        return res;
    }






    /*合并两个有序的数组
    * 给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组
    * 解题思路:从后往前*/

    public void merge(int A[], int m, int B[], int n) {
        //指向数组A的结尾
        int i = m - 1;
        //指向数组B的结尾
        int j = n - 1;
        //指向数组A空间的结尾处
        int k = m + n - 1;
        //从两个数组最大的元素开始，直到某一个数组遍历完
        while(i >= 0 && j >= 0){
            //将较大的元素放到最后
            if(A[i] > B[j])
                A[k--] = A[i--];
            else
                A[k--] = B[j--];
        }
        //数组A遍历完了，数组B还有，则还需要添加到数组A前面
        if(i < 0){
            while(j >= 0)
                A[k--] = B[j--];
        }
        //数组B遍历完了，数组A前面正好有，不用再添加
    }

    /*判断是否为回文字符串
    * 给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。*/
    public boolean judge (String str) {
        // write code here
        int j=str.length()-1;
        int i=0;
        while (i < j){
            if (str.charAt(i) != str.charAt(j)){
                return  false;
            }
            i++;
            j--;
        }
        return true;
    }



}